function Node(range, left, right) {
  this.val = false
  this.range = range
  this.left = left || null
  this.right = right || null
  this.lazy = false
}

class SegmentTree {
  constructor() {
    this.root = new Node([0, 10 ** 9], null, null)
  }

  update(l, r, v, node = null) {
    // const [l, r] = range
    if (l > r) return
    if (node === null) node = this.root
    const [nL, nR] = node.range
    if (nL >= l && nR <= r) {
      node.val = v
      node.lazy = true
      return
    }
    // 动态开点，下传lazy
    this.pushdown(node)

    const mid = (nL + nR) >> 1
    if (l <= mid) this.update(l, r, v, node.left)
    if (r > mid) this.update(l, r, v, node.right)
    this.pushup(node)
  }

  pushdown(node) {
    const [l, r] = node.range
    const mid = (l + r) >> 1
    if (node.left === null) node.left = new Node([l, mid], null, null)
    if (node.right === null) node.right = new Node([mid + 1, r], null, null)
    if (node.lazy) {
      node.left.lazy = true
      node.right.lazy = true
      node.left.val = node.val
      node.right.val = node.val
      node.lazy = false
    }
  }

  pushup(node) {
    node.val = node.left.val && node.right.val
  }

  query(l, r, node = null) {
    if (l > r) return false
    if (node === null) node = this.root
    const [nL, nR] = node.range
    if (nL >= l && nR <= r) return node.val
    this.pushdown(node)
    const mid = (nL + nR) >> 1
    let ans = true
    if (l <= mid) ans = ans && this.query(l, r, node.left)
    if (r > mid) ans = ans && this.query(l, r, node.right)
    return ans
  }
}

/**
 * 线段树解法, 此方法在js里比方法一慢更多
 */
export var RangeModule = function () {
  this.sTree = new SegmentTree()
}

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.addRange = function (left, right) {
  this.sTree.update(left, right - 1, true, this.sTree.root)
}

/**
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
RangeModule.prototype.queryRange = function (left, right) {
  return this.sTree.query(left, right - 1)
}

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.removeRange = function (left, right) {
  this.sTree.update(left, right - 1, false, this.sTree.root)
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * var obj = new RangeModule()
 * obj.addRange(left,right)
 * var param_2 = obj.queryRange(left,right)
 * obj.removeRange(left,right)
 */
